#include <bits/stdc++.h>
#pragma once
using namespace std;


    template <class Key>
    struct DefaultHashfunc{
        size_t operator()(const Key& k){
              return (size_t)k;
        }
    };
    
    

    template<>
    struct DefaultHashfunc<string>{
        size_t operator()(const string &s)
        {
            //BKDR
            size_t hashVal = 0;
            for(auto&ch:s)
            {
                hashVal*=31;
                hashVal+=ch;
            }
            return hashVal;
        }
    };

    template <class T>
    struct HashNode{
        HashNode<T>* n_next;
        T n_data;    
        HashNode(const T& data)
        :n_data(data)
        ,n_next(nullptr)
        {

        }
    };
    

    //前置声明，解决类从下而上寻找不到的问题
    template<class Key,class Val,class KeyOfVal,class HashFunc>    
    class HashTableBuket;

    template <class K, class V, class KeyOfValue, class HF,class Ref,class Ptr>
    struct HSiterator{
        typedef HashNode<V>* I_NodePtr;
        typedef HSiterator<K,V,KeyOfValue,HF,Ref,Ptr> Self;
        typedef const HashTableBuket<K,V,KeyOfValue,HF>* HSBucketPtr;
        HSiterator(const I_NodePtr& p = nullptr,const HSBucketPtr HSp = nullptr,size_t Hashi = -1)
        :m_pHt(HSp)
        ,m_node(p)
        ,HashIndex(Hashi)
        {

        }
        Self& operator++()
        {
            if(m_node->n_next)
                m_node = m_node->n_next;
            else
            {
                HashIndex++;
                m_node = nullptr;
                for(;HashIndex<m_pHt->m_ht.size();HashIndex++)
                {
                    if(m_node=m_pHt->m_ht[HashIndex])
                        break;
                }
            }
            return *this;
        }
        Ref operator*()
        {
            return m_node->n_data;
        }
        Ptr operator->()
        {
            return &(m_node->n_data);
        }
        bool operator==(const Self& it) const
        {
            return m_node == it.m_node;
        }
        bool operator!=(const Self& it) const
        {
            return m_node!=it.m_node;
        }
        Self operator++(int)
        {
            Self tmp = *this;
            if(m_node->n_next)
                m_node = m_node->n_next;
            else
            {
                //找到下一个桶的坐标
                size_t HashBucketIndex = m_pHt->m_hsc(KeyOfValue()(m_node->n_data))+1;
                m_node = nullptr;
                for(;HashBucketIndex<m_pHt->m_ht.size();HashBucketIndex++)
                {
                    if(m_node=m_pHt->m_ht[HashBucketIndex])
                        break;
                }
            }
            return tmp;
        }

        private:
        I_NodePtr m_node;
        HSBucketPtr m_pHt;//用于获取下一个桶
        size_t HashIndex;
    };
    template<class Key,class Val,class KeyOfVal,class HashFunc>    
    class HashTableBuket
    {
        typedef HashTableBuket<Key,Val,KeyOfVal,HashFunc> Self;
        typedef HashNode<Val> Node;
        typedef HashNode<Val>* NodePtr;
        public:
        typedef  HSiterator<Key,Val,KeyOfVal,HashFunc,Val&,Val*> iterator;
        typedef HSiterator<Key,Val,KeyOfVal,HashFunc,const Val&,const Val*> const_iterator;
        friend iterator;
        friend const_iterator;

        private:
        vector<NodePtr> m_ht;
        size_t m_size= 0;
        HashFunc m_hsc;
        KeyOfVal m_Getkey;
        bool Insert(NodePtr cur)
        {
            if(!cur)
            {
                return 0;
            }
            size_t Index = m_hsc(m_Getkey(cur->n_data))%m_ht.size();
            cur->n_next = m_ht[Index];
            m_ht[Index] = cur;
            m_size++;
            return 1;
        }
        public:
        HashTableBuket(size_t size = 10)
        :m_size(0)
        ,m_ht(size,nullptr)
        {

        }
        ~HashTableBuket()
        {
            for(size_t i=0;i<m_ht.size();i++)
            {
                NodePtr cur = m_ht[i];
                while(cur)
                {
                    NodePtr tmp = cur;
                    cur = cur->n_next;
                    delete tmp;
                }
                m_ht[i] = nullptr;
            }
        }
        
        iterator begin()
		{
			for (size_t i = 0; i < m_ht.size(); i++)
			{
				if (m_ht[i])
				{
					return iterator(m_ht[i],this,i);
				}
			}
			return end();
		}

		iterator end()
		{
			return iterator();
		}

		const_iterator cbegin()const
		{
			for (size_t i = 0; i < m_ht.size(); i++)
			{
				if (m_ht[i])
				{
					return const_iterator(m_ht[i],this,i);
				}
			}
			return cend();
		}

		const_iterator cend()const
		{
			return const_iterator();
		}


        pair<pair<NodePtr,bool>,size_t> insert(const Val& data){
            const Key& tmp =m_Getkey(data);
            NodePtr res;
            if(res = find(tmp))
            {
                return make_pair(make_pair(res,false),-1);
            }
            checkSize();
            size_t Index = m_hsc(tmp) %m_ht.size();
            //front_insert
            NodePtr cur = new Node(data);
            cur->n_next = m_ht[Index];
            m_ht[Index] = cur;
            m_size++;
            return make_pair(make_pair(cur,true),Index);
        }
        
        void checkSize()
        {
            if(m_size==m_ht.size())
            {
                Self NewHT(m_ht.capacity()*2);
                for(size_t i =0;i<m_ht.size();i++)
                {
                    NodePtr cur = m_ht[i];
                    m_ht[i] = nullptr;
                    while(cur)
                    {
                        NodePtr tmp = cur;
                        cur = cur->n_next;
                        NewHT.Insert(tmp);
                    }
                }
                NewHT.m_ht.swap(m_ht);
            }
        }
        NodePtr find(const Key& key)
        {
            size_t Index = m_hsc(key)%m_ht.size();
            NodePtr cur = m_ht[Index];
            while(cur)
            {
                if(m_Getkey(cur->n_data)==key)
                {
                    return cur;
                }
                cur = cur->n_next;
            }
            return nullptr;
        }
        bool erase(const Key& k)
        {
            size_t Index = m_hsc(k)%m_ht.size();
            NodePtr cur = m_ht[Index];
            if(cur && m_Getkey(cur->n_data)==k)
            {
                m_ht[Index] = cur->n_next;
                delete cur;
                cur = nullptr;
                return 1;
            }
            while(cur && cur->n_next)
            {
                if(m_Getkey(cur->n_next->n_data) ==k)
                {
                    NodePtr tmp = cur->n_next;
                    cur->n_next = tmp->n_next;
                    delete tmp;
                    return true;
                }
                cur = cur->n_next;
            }
            m_size--;
            return false;
        }
    };

